package com.hao.leetcode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//给定一个 N 叉树，返回其节点值的前序遍历。
//
// 例如，给定一个 3叉树 :
//
//
//
//
//
//
//
// 返回其前序遍历: [1,3,5,6,2,4]。
//
//
//
// 说明: 递归法很简单，你可以使用迭代法完成此题吗? Related Topics 树
// 👍 116 👎 0
public class Demo589 {
    List<Integer> result = new ArrayList<>();
    Stack<Node> stack = new Stack<Node>();

    public static void main(String[] args) {

    }

    //递归
    public List<Integer> preorder(Node root) {
        if (root == null) {
            return result;
        }
        result.add(root.val);
        for (Node node : root.children) {
            preorder(node);
        }
        return result;
    }

    //循环
    public List<Integer> preorder2(Node root) {
        if (root == null) {
            return result;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            result.add(node.val);
            for (int i = node.children.size() - 1; i >= 0; i--) {
                stack.push(node.children.get(i));
            }
        }
        return result;
    }
}
